package easy;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedHashMap;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;
import java.util.Stack;

public class Solution_234 {

    public static TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        /*List<TreeNode> list1 = new ArrayList<>();
        find(root, p, list1);
        List<TreeNode> list2 = new ArrayList<>();
        find(root, q, list2);
        int length1 = list1.size();
        int length2 = list2.size();
        int length = Math.min(list1.size(), list2.size());
        TreeNode target = null;
        for (int i = 1; i <= length; i++) {
            if (list1.get(length1-i).val==list2.get(length2-i).val) {
                target = list1.get(length1-i);
            }
        }
        return target;*/
        Map<TreeNode, Integer> map = new LinkedHashMap<>();
        find(root, p, q, map);
        for (TreeNode treeNode : map.keySet()) {
            if (map.get(treeNode)==2) {
                return treeNode;
            }
        }
        return null;
    }

    public static int find(TreeNode root, TreeNode p, TreeNode q, Map<TreeNode, Integer> map) {
        if (root==null) return 0;
        Integer count;
        int l = find(root.left, p, q, map);
        int r = find(root.right, p, q, map);
        count = map.getOrDefault(root, 0);
        count += l;
        count += r;
        if (p.val==root.val) {
            count++;
        }
        if (q.val==root.val) {
            count++;
        }
        map.put(root, count);
        return count;
    }


    public static boolean find(TreeNode root, TreeNode target, List<TreeNode> list) {
        if (root.val == target.val) {
            list.add(root);
            return true;
        }
        boolean find = false;
        if (root.left!=null) {
            find = find(root.left, target, list);
        }
        if (!find && root.right!=null) {
            find = find(root.right, target, list);
        }
        if (find) {
            list.add(root);
        }
        return find;
    }

    public static void main(String[] args) {
        TreeNode head = new TreeNode(6);
        head.left = new TreeNode(2);
        head.right = new TreeNode(8);
        head.left.left = new TreeNode(0);
        head.left.right = new TreeNode(4);
        head.left.right.left = new TreeNode(3);
        head.left.right.right = new TreeNode(5);
        head.right.left = new TreeNode(7);
        head.right.right = new TreeNode(9);
        TreeNode target = new TreeNode(0);
        TreeNode target2 = new TreeNode(5);
        LinkedHashMap<TreeNode, Integer> map = new LinkedHashMap<>();
//        find(head, target, target2, map);
//        List<TreeNode> list = new ArrayList<>();
//        find(head, target, list);
//        head.next.next.next.next = new TreeNode(1);
        System.out.println(lowestCommonAncestor(head, target, target2).val);

    }

    public static class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode(int x) { val = x; }
  }
}
